package stark;

public class 目标和 {
    public static void main(String[] args) {
        int[] ints = {1, 1, 1, 1, 1};
        int target = 3;
        Solution solution = new Solution();
        int targetSumWays = solution.findTargetSumWays(ints, target);
        System.out.println(targetSumWays);

    }
    static class Solution {
        int count = 0;

        public int findTargetSumWays(int[] nums, int target) {
            backtrack(nums, target, 0, 0);
            return count;
        }

        public void backtrack(int[] nums, int target, int index, int sum) {
            if (index == nums.length) {
                if (sum == target) {
                    count++;
                }
            } else {
                backtrack(nums, target, index + 1, sum + nums[index]);
                backtrack(nums, target, index + 1, sum - nums[index]);
            }
        }
    }

}
